/************************************************************************

								Heroes IV
					  Copyright 2000, The 3DO Company

	------------------------------------------------------------------
  						       sorted_clip_list.h

	$Header: /game/sorted_clip_list.h $

	$NoKeywords: $

 ************************************************************************/

// kill the 255+ character identifier warning.  Templates tend to exceed that easily.
#include "precompiled.h"
#pragma warning( disable: 4786 )

#include "sorted_clip_list.h"
#include "debug_message.h"

#include <cassert>

int g_node_searched = 0;
int g_rects_seached = 0;

void check_for_duplicates ( t_sorted_clip_list::t_rect_list & m_rects );

namespace {

	const float k_intersect_threshold_precent	= .75f;
	const float k_insert_threshold_precent		= .75f;
	const float k_remove_threshold_precent		= .75f;

	const int	k_remove_rect_count_threshold		= 20;
	const int	k_insert_rect_count_threshold		= 20;
	const int	k_intersect_rect_count_threshold	= 20;

	bool  g_enable_flag = true;

	const int k_min_quad_width	= 50;
	const int k_min_quad_height = 50;
};

int calcualte_quadtree_size(int size)
{
	int sum = 0;

	for (int i = 1; i <= size; i++)
		sum += pow((double)4,(double)i);

	return sum;
}

t_sorted_clip_list::t_sorted_clip_list( )
{
	//depending upon the subdivision level we preallocate the nodes to avoid the run
	//time cost of constantly deleting / allocating nodes.

	m_global_free_rect_list		= get_global_free_rect_list();

	m_quadtree_array.resize(0);
	m_sub_division_level		=0;
	m_quadtree_array_size		=0;
	m_intersect_threshold		=0;
	m_insert_threshold			=0;
	m_remove_threshold			=0;
}

t_sorted_clip_list::t_sorted_clip_list( int sub_division_level , t_screen_rect extent )
{
	//depending upon the subdivision level we preallocate the nodes to ainline void the run
	//time cost of constantly deleting / allocating nodes.

	m_global_free_rect_list		= get_global_free_rect_list();

	m_quadtree_array.resize(0);
	m_sub_division_level		=0;
	m_quadtree_array_size		=0;
	m_intersect_threshold		=0;
	m_insert_threshold			=0;
	m_remove_threshold			=0;

	preallocate_quadtree_nodes( sub_division_level, extent );
}

t_sorted_clip_list::~t_sorted_clip_list()
{
	m_global_free_rect_list->clear_rect_list(m_rects);
	m_global_free_rect_list->clear_rect_list(m_split_list);

	m_global_free_rect_list = NULL;
}

bool t_sorted_clip_list::preallocate_quadtree_nodes( t_screen_rect extent )
{
	//let the program decide what level to create the tree based upon the extent.
	int width  = extent.width();
	int height = extent.height();

	int min_resolution_width	= width/k_min_quad_width;
	int min_resolution_height	= height/k_min_quad_height;
	
	int tree_resolution = (sqrt( ((double)min_resolution_width + min_resolution_height )/2));

	return preallocate_quadtree_nodes( tree_resolution, extent );
}

bool t_sorted_clip_list::preallocate_quadtree_nodes( int sub_division_level, t_screen_rect extent )
{
	//sub_division level defines how many levels deep the quadtree goes.
	//the total_number_nodes

	//4 levels deep , the limit currently.

	if (sub_division_level > 4)
		sub_division_level = 4;

	int total_number_nodes =  calcualte_quadtree_size( sub_division_level );

	m_sub_division_level	= sub_division_level;
	m_quadtree_array_size	= total_number_nodes;

	m_quadtree_array.reserve(m_quadtree_array_size);
	m_quadtree_array.resize(m_quadtree_array_size);

	int current_level = 0;
	int current_index = 0;

	m_parent_node.area = extent;

	bool val = assign_nodes(&m_parent_node, current_index, current_level);

	if (val == false)
	{
		//error with node filling
		assert(0);

		return false;
	}
	
	clear(extent);

	m_intersect_threshold		= ((float)extent.width()*extent.height()) * k_intersect_threshold_precent;
	m_insert_threshold			= ((float)extent.width()*extent.height()) * k_insert_threshold_precent;
	m_remove_threshold			= ((float)extent.width()*extent.height()) * k_remove_threshold_precent;

	return true;
}

bool t_sorted_clip_list::assign_nodes( t_quadtree_node* parent_node, int & current_index, int current_level)
{
	//assign the block of 4 nodes child to node
	
	current_level++;

	if (current_level > m_sub_division_level)
		return true;

	parent_node->node_a = current_index++;
	parent_node->node_b = current_index++;
	parent_node->node_c = current_index++;
	parent_node->node_d = current_index++;

	bool val = calcuate_quadtree_child_area(	
									m_quadtree_array[parent_node->node_a].area,
									m_quadtree_array[parent_node->node_b].area,
									m_quadtree_array[parent_node->node_c].area,
									m_quadtree_array[parent_node->node_d].area,
									parent_node->area);
	if (val == false)
		return false;

	if (assign_nodes( &m_quadtree_array[parent_node->node_a],  current_index,  current_level) == false) 
		return false;

	if (assign_nodes( &m_quadtree_array[parent_node->node_b],  current_index,  current_level) == false) 
		return false;

	if (assign_nodes( &m_quadtree_array[parent_node->node_c],  current_index,  current_level) == false) 
		return false;

	if (assign_nodes( &m_quadtree_array[parent_node->node_d],  current_index,  current_level) == false) 
		return false;

	return true;
}

/////////////////////////////////////////
//		a  |  b 
//		-------
//		c  |  d
////////////////////////////////////////

bool t_sorted_clip_list::calcuate_quadtree_child_area(	
								t_screen_rect & area_a,
								t_screen_rect & area_b,
								t_screen_rect & area_c,
								t_screen_rect & area_d,
								t_screen_rect & area_parent
							 )
{
	//the child areas do not share edges
	//the top and left edge is owned by the current area, the lower and bottom edge
	//is owned by the neighboring areas.

	int half_width  = area_parent.width()/2;
	int half_height = area_parent.height()/2;
	
	area_a.top		= area_parent.top;
	area_a.left		= area_parent.left;
	area_a.bottom	= area_parent.top	+ half_height-1;
	area_a.right	= area_parent.left	+ half_width -1;
	
	area_b.top		= area_parent.top;
	area_b.left		= area_parent.left	+ half_width;
	area_b.bottom	= area_parent.top	+ half_height-1;
	area_b.right	= area_parent.right;
	
	area_c.top		= area_parent.top	+ half_height;
	area_c.left		= area_parent.left;
	area_c.bottom	= area_parent.bottom;
	area_c.right	= area_parent.left	+ half_width-1;
	
	area_d.top		= area_parent.top	+ half_height;
	area_d.left		= area_parent.left	+ half_width;
	area_d.bottom	= area_parent.bottom;
	area_d.right	= area_parent.right;

	return true;
}

void t_sorted_clip_list::intersect( t_screen_rect const & query_area , t_rect_list & result )
{
	//to find all the rects that intersect with the given rectangle, we walk the tree 
	
	if ( ((query_area.width()*query_area.height()) > m_intersect_threshold  || 
			m_rects.size() < k_intersect_rect_count_threshold  ) && g_enable_flag )
	{
		t_screen_rect				local_rect		= query_area;
		t_rect_list::iterator		rect_iterator	= m_rects.begin();
		t_screen_rect				center;

		m_global_free_rect_list->clear_rect_list(m_split_list);
	
		while (rect_iterator != m_rects.end())
		{
			if (::intersect(*rect_iterator, local_rect) == true)
			{
				center = intersection( local_rect, *rect_iterator );
				
				if (center.width() < 0 || center.height() < 0)
				{
					rect_iterator++;
					continue;
				}
				
				m_global_free_rect_list->push_back_use_free_list(m_split_list,center);
			}
			
			rect_iterator++;
		}
		
		rect_iterator = m_split_list.begin();

		while(rect_iterator != m_split_list.end())
		{
			result.push_back(*rect_iterator);
			rect_iterator++;
		}
	
		m_global_free_rect_list->clear_rect_list(m_split_list);
	
		return;
	}

	int intial_depth = 0;

	intersect(m_parent_node, query_area, result, intial_depth);

	return;
}

 void t_sorted_clip_list::insert( t_screen_rect const & insert_rect_var, bool splitable )
{

	//put the insert_rect into the tree

	//-check the insert_rect against each node starting with the parent.
	//-if the insert_rect interects or is contained wihin a child area walk down that
	//		childs nodes
	//			a)if intersect, walk down child node
	//			b)if contained, walk only down this child node, all others can be ignored
	//-if the insert_rect contains any rects , reomve them from the list
	//-if the insert_rect overlaps any of the rects splitable them into new rects
	
	bool						can_insert_rect		= true;
	int							inital_depth		= 0;
	t_screen_rect				local_rect			= insert_rect_var;

	m_global_free_rect_list->clear_rect_list(m_split_list);
	
	if (((insert_rect_var.width()*insert_rect_var.height()) > m_insert_threshold  || 
		m_rects.size() < k_insert_rect_count_threshold ) && g_enable_flag)
	{
		t_rect_list::iterator		rect_iterator = m_rects.begin();
		t_rect_list::iterator		next_rect_iterator;
		
		while (rect_iterator != m_rects.end())
		{
			next_rect_iterator = rect_iterator;
			next_rect_iterator++;

			if (::intersect(local_rect, *rect_iterator) == false)
			{
				rect_iterator = next_rect_iterator;
				continue;
			}
			
			if ( rect_iterator->contains(local_rect) )
			{
				return;
			}

			if (local_rect.contains(*rect_iterator) == true)
			{
				m_global_free_rect_list->add_to_free_list(m_rects,rect_iterator);
				
				rect_iterator = next_rect_iterator;
				
				continue;
			}

			if (split_rect(local_rect, *rect_iterator, m_split_list ) == true)
			{
				//remove this rect from the list as it has been split
				
				m_global_free_rect_list->add_to_free_list(m_rects,rect_iterator);
				
				rect_iterator = next_rect_iterator;
				
				continue;
			}

			rect_iterator = next_rect_iterator;
		}

		merge_rects_with(local_rect, m_split_list);
		
		m_global_free_rect_list->push_back_use_free_list(m_rects,local_rect);

		m_rects.splice(m_rects.begin(),m_split_list,m_split_list.begin(),m_split_list.end());
		
		resort_all();
		
		return;
	}
	
	//split the tree against the rect

	insert_rect_into_tree( m_parent_node, local_rect, m_split_list, inital_depth, can_insert_rect );

	//reinsert the split rects into the tree
	
	if (can_insert_rect)
	{
		merge_rects_with(local_rect, m_split_list);	
		
		if (m_split_list.size() != 0)
		{	
			std::list<t_screen_rect>::iterator			iter;
			t_quadtree_node*							insert_split_node;
			
			for (iter = m_split_list.begin(); iter != m_split_list.end(); iter++)
			{
				if (iter->width() > 0 && iter->height() > 0)
				{
					insert_split_node = find_insert_node( m_parent_node, *iter, inital_depth );
					add_rect( *insert_split_node, *iter);
				}
			}
		}
	}
	
	//add the new rect into the tree
	//find the insertion node

	if (can_insert_rect)
	{
		if (local_rect.width() > 0 && local_rect.height() > 0)
		{
			t_quadtree_node* insert_node = find_insert_node( m_parent_node, local_rect, inital_depth);
			add_rect( *insert_node, local_rect);
		}
	}

	m_global_free_rect_list->clear_rect_list(m_split_list);

	return;
}

 void t_sorted_clip_list::insert( t_screen_rect_list const & insert_rect_list, bool splitable )
{
	 t_screen_rect_list::const_iterator rect_iterator = insert_rect_list.begin();

	 while(rect_iterator != insert_rect_list.end())
	 {
		 insert(*rect_iterator++, splitable);
	 }

	 return;
}
 
void t_sorted_clip_list::intersect( t_screen_rect const & query_area )
{
	int intial_depth = 0;

	t_screen_rect local_rect = query_area;

	//if the area is large enough its better to perform a linear search and resort the tree
	if ( ((query_area.width()*query_area.height()) > m_intersect_threshold  || 
		m_rects.size() < k_intersect_rect_count_threshold  )&& g_enable_flag )
	{
		t_rect_list::iterator		rect_iterator = m_rects.begin();
		t_rect_list::iterator		next_rect_iterator;
		
		m_global_free_rect_list->clear_rect_list(m_split_list);

		while (rect_iterator != m_rects.end())
		{
			next_rect_iterator = rect_iterator;
			next_rect_iterator++;
			
			if (::intersect(local_rect, *rect_iterator) == false)
			{
				m_global_free_rect_list->add_to_free_list(m_rects,rect_iterator);
			}

			rect_iterator = next_rect_iterator;
		}

		resort_all();

		return;
	}

	intersect(m_parent_node, query_area, m_split_list, intial_depth);

	m_global_free_rect_list->clear_rect_list(m_rects);

	m_rects.swap(m_split_list);

	resort_all();

	check_m_rects();

	return;
}

 void t_sorted_clip_list::remove( t_screen_rect const & remove_rect_area )
{
	//clip the remove_rect against the rects contained within the tree

	//-check the remove_rect against each node starting with the parent.
	//-if the remove_rect interects or is contained wihin a child area walk down that
	//		childs nodes
	//			a)if intersect, walk down child node
	//			b)if contained, walk only down this child node, all others can be ignored
	//-if the remove_rect contains any rects , reomve them from the list
	//-if the remove_rect overlaps any of the rects, split them into new rects, remove the ones which 
	//		are contained within the remove rect, add the new splitable rects (might be able to sort down 
	//		to increase efficency)

	bool						can_modify_source	= false;
	int							inital_depth		= 0;
	t_screen_rect				local_rect			= remove_rect_area;

	m_global_free_rect_list->clear_rect_list(m_split_list);

	//if the area is large enough its better to perform a linear search and resort the tree
	if (((remove_rect_area.width()*remove_rect_area.height()) > m_remove_threshold || 
		m_rects.size() < k_remove_rect_count_threshold)  && g_enable_flag)
	{
		t_rect_list::iterator		rect_iterator = m_rects.begin();
		t_rect_list::iterator		next_rect_iterator;

		m_global_free_rect_list->clear_rect_list(m_split_list);
		
		while (rect_iterator != m_rects.end())
		{
			next_rect_iterator = rect_iterator;
			next_rect_iterator++;
			
			if (::intersect(local_rect, *rect_iterator) == false)
			{
				rect_iterator = next_rect_iterator;
				continue;
			}
			
			if (split_rect( local_rect, *rect_iterator, m_split_list ) == true)
				m_global_free_rect_list->add_to_free_list(m_rects,rect_iterator);
			
			rect_iterator = next_rect_iterator;
		}
		
		m_rects.splice(m_rects.begin(),m_split_list,m_split_list.begin(),m_split_list.end());

		resort_all();
		
		m_global_free_rect_list->clear_rect_list(m_split_list);

		return;
	}

	//split the tree against the rect

	split_tree_against_rect( m_parent_node, local_rect, m_split_list, inital_depth );

	//reinsert the split rects into the tree

	int split_size = m_split_list.size();

	if (!m_split_list.empty())
	{
		std::list<t_screen_rect>::iterator			iter;
		
		for (iter = m_split_list.begin(); iter != m_split_list.end(); iter++)
		{
			if (iter->width() > 0 && iter->height() > 0)
			{
				t_quadtree_node* insert_split_node = find_insert_node( m_parent_node, *iter, inital_depth );
				add_rect( *insert_split_node, *iter);
			}
		}
	}
	
	m_global_free_rect_list->clear_rect_list(m_split_list);
	
	return;
}

inline void t_sorted_clip_list::intersect( t_quadtree_node& parent_node, t_screen_rect const & query_area , t_rect_list & result, int depth)
{

	//to find all the rects that intersect with the given rectangle, we walk the tree 

	//-if the query_area contains the full extent, then return the entire list of rects
	//-check the query_area against each node starting with the parent.
	//-if the query_area interects or is contained wihin a child area walk down that
	//		childs nodes
	//			a)if intersect, walk down child node
	//			b)if contained, walk only down this child node, all others can be ignored
	
	intersect_rect( parent_node, query_area, result );

	depth++;

	if (depth > m_sub_division_level)
		return;

	//query for containment ( early out )///////////////////////////////////////////////
	//stop search if containment is found.
	
	if (m_quadtree_array[parent_node.node_a].area.contains( query_area ) == true)
	{
		intersect( m_quadtree_array[parent_node.node_a], query_area, result, depth );
		return;
	}
	
	if (m_quadtree_array[parent_node.node_b].area.contains( query_area ) == true)
	{
		intersect( m_quadtree_array[parent_node.node_b], query_area, result, depth );
		return;
	}
	
	if (m_quadtree_array[parent_node.node_c].area.contains( query_area ) == true)
	{
		intersect( m_quadtree_array[parent_node.node_c], query_area, result, depth );
		return;
	}
	
	if (m_quadtree_array[parent_node.node_d].area.contains( query_area ) == true)
	{
		intersect( m_quadtree_array[parent_node.node_d], query_area, result, depth );
		return;
	}

	//query each child_node/////////////////////////////////////////////////////////////

	if (::intersect(m_quadtree_array[parent_node.node_a].area, query_area)==true)
	{
		intersect( m_quadtree_array[parent_node.node_a], query_area, result, depth );
	}
	
	if (::intersect(m_quadtree_array[parent_node.node_b].area, query_area)==true)
	{	
		intersect( m_quadtree_array[parent_node.node_b], query_area, result, depth );
	}
		
	if (::intersect(m_quadtree_array[parent_node.node_c].area, query_area)==true)
	{
		intersect( m_quadtree_array[parent_node.node_c], query_area, result, depth );
	}
			
	if (::intersect(m_quadtree_array[parent_node.node_d].area, query_area)==true)
	{
		intersect( m_quadtree_array[parent_node.node_d], query_area, result, depth );
	}

	return;
}

inline void t_sorted_clip_list::merge_rects_with( t_screen_rect & query_rect, t_rect_list & merge_list )
{
	if (merge_list.empty())
		return;

	t_rect_list::iterator    index = merge_list.begin();
	t_rect_list::iterator    next ;
	t_screen_rect			 current_rect;

	while (true)
	{
		// find a rectangle which shares an edge with the current rectangle.
		while (index != merge_list.end())
		{
			current_rect = *index;

			// is it directly above or below?
			if (query_rect.left == current_rect.left && query_rect.right == current_rect.right)
			{
				if (query_rect.bottom == current_rect.top)
				{
					query_rect.bottom = current_rect.bottom;
					break;
				}
				if (query_rect.top == current_rect.bottom)
				{
					query_rect.top = current_rect.top;
					break;
				}
			}

			// is it directly left or right?
			if (query_rect.top == current_rect.top && query_rect.bottom == current_rect.bottom)
			{
				if (query_rect.right == current_rect.left)
				{
					query_rect.right = current_rect.right;
					break;
				}
				if (query_rect.left == current_rect.right)
				{
					query_rect.left = current_rect.left;
					break;
				}
			}

			index++;
		}

		// if we found and merged a rectangle, delete it.  Else stop.
		if (index != merge_list.end())
		{
			next = index;
			next++;

			m_global_free_rect_list->add_to_free_list( merge_list, index );

			index = next;
		}
		else
			break;
	}
}

inline void t_sorted_clip_list::add_rect( t_quadtree_node & quad_node, t_screen_rect & insert_rect )
{
	//the quad nodes hold iterators to the rects which they point to the m_rects list, which contains all 
	//the rects, this allows for fast iterating through the entire rect list without using recursing through
	//the tree.

	m_global_free_rect_list->push_back_use_free_list(m_rects,insert_rect);

	quad_node.rect_iterator_list.push_back(--m_rects.end());

	return;
}

inline void t_sorted_clip_list::intersect_rect( t_quadtree_node & quad_node, t_screen_rect const & query_rect, t_rect_list & results )
{
	//-check the insert_rect against the list
	//-if there is an intersecting or contained rect. 
	//-remove those rects and put those splitable rects into the split_list
	
	if (quad_node.rect_iterator_list.empty()) 
		return;

	t_rect_iterator_list::iterator iter = quad_node.rect_iterator_list.begin();
	t_screen_rect		center;

	while( iter != quad_node.rect_iterator_list.end() )
	{
		if (::intersect(query_rect,**iter) == true)
		{
			g_rects_seached++;
			center = intersection( query_rect, **iter );

			if (center.width() > 0 && center.height() > 0)
				results.push_back(center);
		}

		iter++;
	}

	return;
}

inline void t_sorted_clip_list::insert_rect_into_tree( t_quadtree_node & parent_node, t_screen_rect & insert_rect_var, t_rect_list & split_list, int depth, bool & can_insert_rect )
{
	insert_rect( parent_node, insert_rect_var, split_list, can_insert_rect );

	//the query_area has been wholely consumed by an existing rectangle.
	if (can_insert_rect == false)
		return;

	depth++;

	if (depth > m_sub_division_level)
		return;

	//query each child_node/////////////////////////////////////////////////////////////

	if (::intersect(m_quadtree_array[parent_node.node_a].area, insert_rect_var)==true)
		insert_rect_into_tree( m_quadtree_array[parent_node.node_a], insert_rect_var, split_list, depth, can_insert_rect );
	
	if (::intersect(m_quadtree_array[parent_node.node_b].area, insert_rect_var)==true)
		insert_rect_into_tree( m_quadtree_array[parent_node.node_b], insert_rect_var, split_list, depth, can_insert_rect );

	if (::intersect(m_quadtree_array[parent_node.node_c].area, insert_rect_var)==true)
		insert_rect_into_tree( m_quadtree_array[parent_node.node_c], insert_rect_var, split_list, depth, can_insert_rect );
	
	if (::intersect(m_quadtree_array[parent_node.node_d].area, insert_rect_var)==true)
		insert_rect_into_tree( m_quadtree_array[parent_node.node_d], insert_rect_var, split_list, depth, can_insert_rect );

	return;
}

inline void t_sorted_clip_list::insert_rect( t_quadtree_node & quad_node, t_screen_rect & insert_rect, t_rect_list & split_list, bool & can_insert_rect )
{
	//-check the insert_rect against the list
	//-if there is an intersecting or contained rect. 
	//-remove those rects and put those splitable rects into the split_list

	if (quad_node.rect_iterator_list.empty()) 
		return;

	t_rect_iterator_list::iterator iter = quad_node.rect_iterator_list.begin();

	while( iter != quad_node.rect_iterator_list.end() )
	{
		if (::intersect(insert_rect,**iter) == true)
		{
			//split this rect using our splitable algorithim
		
			if ( (**iter).contains(insert_rect) )
			{
				can_insert_rect = false;

				break;
			}

			if (insert_rect.contains(**iter) == true)
			{
				m_global_free_rect_list->add_to_free_list(m_rects,*iter);
				
				iter = quad_node.rect_iterator_list.erase(iter);
				
				check_m_rects();
				
				continue;
			}

			if (split_rect(insert_rect, **iter, split_list ) == true)
			{
				//remove this rect from the list as it has been split

				m_global_free_rect_list->add_to_free_list(m_rects,*iter);
				
				iter = quad_node.rect_iterator_list.erase(iter);
				
				check_m_rects();
				
				continue;
			}
		}

		iter++;
	}
}

inline void t_sorted_clip_list::check_m_rects()
{
}

inline void t_sorted_clip_list::split_rect( t_quadtree_node & quad_node, t_screen_rect & insert_rect, t_rect_list & split_list )
{
	//-check the insert_rect against the list
	//-if there is an intersecting or contained rect. 
	//-remove those rects and put those splitable rects into the split_list

	if (quad_node.rect_iterator_list.empty()) 
		return;

	t_rect_iterator_list::iterator iter = quad_node.rect_iterator_list.begin();

	while( iter != quad_node.rect_iterator_list.end() )
	{
		if (::intersect(insert_rect,**iter) == true)
		{
			//split this rect using our splitable algorithim
		
			if (insert_rect.contains(**iter) == true)
			{
				m_global_free_rect_list->add_to_free_list(m_rects,*iter);
				
				iter = quad_node.rect_iterator_list.erase(iter);
				
				check_m_rects();
				
				continue;
			}

			if (split_rect(insert_rect, **iter, split_list ) == true)
			{
				//remove this rect from the list as it has been split
				
				m_global_free_rect_list->add_to_free_list(m_rects,*iter);
				
				iter = quad_node.rect_iterator_list.erase(iter);
				
				check_m_rects();
				
				continue;
			}
		}

		iter++;
	}
}

inline bool t_sorted_clip_list::split_rect( t_screen_rect  & major_rect, t_screen_rect & minor_rect, t_rect_list & split_list )
{
	//we perform 2 splitable paths and take the result of the lower number of resulting rects. -TODO

	t_screen_rect intersect_rect;
	t_screen_rect new_rect;
	
	intersect_rect = intersection( major_rect, minor_rect );
	
	if (intersect_rect.width() < 0 || intersect_rect.height() < 0)
		return false;

	// determine what remains of the rectangle after we remove the new one.

	new_rect		= minor_rect;
	new_rect.bottom = intersect_rect.top;
	
	if (new_rect.height() > 0)
		m_global_free_rect_list->push_back_use_free_list( split_list, new_rect );
	
	new_rect.top		= intersect_rect.top;
	new_rect.bottom		= intersect_rect.bottom;
	new_rect.right		= intersect_rect.left;
	
	if (new_rect.width() > 0)
		m_global_free_rect_list->push_back_use_free_list( split_list, new_rect );

	new_rect.left		= intersect_rect.right;
	new_rect.right		= minor_rect.right;
	
	if (new_rect.width() > 0)
		m_global_free_rect_list->push_back_use_free_list( split_list, new_rect );

	new_rect			= minor_rect;   
	new_rect.top		= intersect_rect.bottom;
	
	if (new_rect.height() > 0) 
		m_global_free_rect_list->push_back_use_free_list( split_list, new_rect );
	
	return true;
}

inline void t_sorted_clip_list::split_tree_against_rect(t_quadtree_node & parent_node, t_screen_rect & query_area, t_rect_list & split_list, int depth )
{
	split_rect( parent_node, query_area, split_list );

	depth++;

	if (depth > m_sub_division_level)
		return;

	//query each child_node/////////////////////////////////////////////////////////////

	if (::intersect(m_quadtree_array[parent_node.node_a].area, query_area)==true)
		split_tree_against_rect( m_quadtree_array[parent_node.node_a], query_area, split_list, depth );
	
	if (::intersect(m_quadtree_array[parent_node.node_b].area, query_area)==true)
		split_tree_against_rect( m_quadtree_array[parent_node.node_b], query_area, split_list, depth );

	if (::intersect(m_quadtree_array[parent_node.node_c].area, query_area)==true)
		split_tree_against_rect( m_quadtree_array[parent_node.node_c], query_area, split_list, depth );
	
	if (::intersect(m_quadtree_array[parent_node.node_d].area, query_area)==true)
		split_tree_against_rect( m_quadtree_array[parent_node.node_d], query_area, split_list, depth );

	return;
}

bool quadnode_intersect_with_rect( t_quadtree_node & quad_node, t_screen_rect & rect )
{
	bool intersect = ::intersect(quad_node.area, rect);
	bool contain   = quad_node.area.contains( rect );

	if (quad_node.area.top		<= rect.top		&&
		quad_node.area.bottom	>= rect.bottom	&&
		quad_node.area.left		<= rect.left	&&
		quad_node.area.right	>= rect.right)
		contain = true;

	return intersect && !contain;
}

inline t_quadtree_node* t_sorted_clip_list::find_insert_node( t_quadtree_node & parent_node, t_screen_rect & insert_rect, int depth )
{
	//find the node which can contain the insert_rect

	depth++;

	if (depth > m_sub_division_level)
		return &parent_node;
	
	//query each child_node/////////////////////////////////////////////////////////////
	//if the next level exceeds our depth limit, then this is the last node which we can insert 
	//the rect into the tree.

	if (m_quadtree_array[parent_node.node_a].area.contains( insert_rect ) == true)
		return find_insert_node( m_quadtree_array[parent_node.node_a], insert_rect, depth );
	
	if (m_quadtree_array[parent_node.node_b].area.contains( insert_rect ) == true)
		return find_insert_node( m_quadtree_array[parent_node.node_b], insert_rect, depth );
	
	if (m_quadtree_array[parent_node.node_c].area.contains( insert_rect ) == true)
		return find_insert_node( m_quadtree_array[parent_node.node_c], insert_rect, depth );
	
	if (m_quadtree_array[parent_node.node_d].area.contains( insert_rect ) == true)
		return find_insert_node( m_quadtree_array[parent_node.node_d], insert_rect, depth );

	return &parent_node;
}

inline void t_sorted_clip_list::resort_all()
{
	//clear the quadtree aray lists

	check_m_rects();

	m_global_free_rect_list->clear_rect_list(m_split_list);

	std::vector<t_quadtree_node>::iterator   quad_node_iterator = m_quadtree_array.begin();

	m_parent_node.rect_iterator_list.clear();

	while(quad_node_iterator != m_quadtree_array.end())
	{
		if (!quad_node_iterator->rect_iterator_list.empty())
			quad_node_iterator->rect_iterator_list.clear();
		quad_node_iterator++;
	}

	//resort the rects in m_rects

	t_rect_iterator		rect_iterator;
	t_quadtree_node*	insert_node;
	int					inital_depth = 0;
	
	for(rect_iterator = m_rects.begin(); rect_iterator != m_rects.end(); rect_iterator++)
	{
		insert_node = find_insert_node( m_parent_node, *rect_iterator, inital_depth);
		insert_node->rect_iterator_list.push_back(rect_iterator);
	}

	//update_extent();
	
	check_m_rects();

	return;
}

inline void t_sorted_clip_list::update_extent()
{
	check_m_rects();

	if (m_rects.empty())
	{
		m_extent = t_screen_rect(0,0,0,0);
		return;
	}
	
	t_rect_iterator index = m_rects.begin();
	
	m_extent = *index++;

	t_screen_rect rect;

	while (index != m_rects.end())
	{
		//t_screen_rect( int left, int top, int right, int bottom );
		//m_extent = ::get_extent( m_extent, *index++ );
		
		rect  = *index;

		index++;

		m_extent.left	= rect.left   < m_extent.left   ? rect.left		: m_extent.left;
		m_extent.top	= rect.top    < m_extent.top    ? rect.top		: m_extent.top;
		m_extent.right	= rect.right  > m_extent.right  ? rect.right	: m_extent.right;
		m_extent.bottom = rect.bottom > m_extent.bottom ? rect.bottom	: m_extent.bottom;
	}

	check_m_rects();

	return;
}

 void t_sorted_clip_list::offset( t_screen_point const & offset )
{	
	check_m_rects();

	t_rect_iterator iterator;
	
	for (iterator = m_rects.begin(); iterator != m_rects.end(); iterator++)
	{
		*iterator += offset;
	}
	
	resort_all();
	
	check_m_rects();
	
	return;
}

 void t_sorted_clip_list::clear( t_screen_rect const & new_area )
{
	check_m_rects();

	//clear the quadtree aray lists

	std::vector<t_quadtree_node>::iterator   quad_node_iterator = m_quadtree_array.begin();

	m_parent_node.rect_iterator_list.clear();

	while(quad_node_iterator != m_quadtree_array.end())
	{
		if (!quad_node_iterator->rect_iterator_list.empty())
			quad_node_iterator->rect_iterator_list.clear();
		quad_node_iterator++;
	}

	//clear out the rects list

	m_global_free_rect_list->clear_rect_list(m_rects);

	//insert the new rect

	insert( new_area, false );

	//update_extent();

	check_m_rects();

	return;
}
 
void check_for_duplicates ( t_sorted_clip_list::t_rect_list & m_rects )
{
 
	 t_sorted_clip_list::t_rect_list::iterator		outer_iterator;
	 t_sorted_clip_list::t_rect_list::iterator		inner_iterator;
	 
	 outer_iterator = m_rects.begin();
	 
	 int intersect_counter =  0;
	 
	 RELEASE_MESSAGE( format_string("m_rect size %i\n", m_rects.size()).c_str() );
	 
	 t_screen_rect intersect_rect;
	 
	 int avg_width=0;
	 int avg_height=0;
	 
	 int duplicate_count = 0;
	 
	 int half_count = m_rects.size()/2 + 1;
	 int count = 0;
	 
	 while(outer_iterator != m_rects.end())
	 {
		 inner_iterator = outer_iterator;
		 inner_iterator++;
		 count++;
		 
		 if (count == half_count) 
			 break;
		 
		 while(inner_iterator != m_rects.end())
		 {
			 if (::intersect(*outer_iterator,*inner_iterator))
			 {
				 t_screen_rect outer = *outer_iterator;
				 t_screen_rect inner = *inner_iterator;
				 
				 intersect_rect = ::intersection(outer,inner);
				 
				 if (outer == inner)
				 {
					 duplicate_count++;
					 
					 if (outer.contains(inner))
					 {
						 int containment = 1;
					 }
				 }
				 
				 if (intersect_rect.width() > 0 && intersect_rect.height() > 0)
				 {
					// RELEASE_MESSAGE( format_string("OUT : %i l, %i t, %i r, %i b \n", outer.left, outer.top, outer.right, outer.bottom).c_str() );
					 //RELEASE_MESSAGE( format_string("IN  : %i l, %i t, %i r, %i b \n", inner.left, inner.top, inner.right, inner.bottom).c_str() );
					 
					 avg_width += intersect_rect.width();
					 avg_height += intersect_rect.height();
					 intersect_counter++;
				 }
			 }
			 
			 inner_iterator++;
		 }
		 
		 outer_iterator++;
	 }

	if (intersect_counter > 0 || duplicate_count > 0)
	{
		RELEASE_MESSAGE( format_string("%i intersections within the rect list\n", intersect_counter).c_str() );
		RELEASE_MESSAGE( format_string("%i duplicates\n", duplicate_count).c_str() );
		RELEASE_MESSAGE( format_string("%i x %i avg_width x avg_height\n", avg_width/intersect_counter, avg_height/intersect_counter).c_str() );
	}
}

void t_sorted_clip_list::verify_tree()
{
	return;

	//check the tree 

	//check if the m_rects has any overlaping rects.

	//return;

	t_rect_list::iterator		outer_iterator;
	t_rect_list::iterator		inner_iterator;

	outer_iterator = m_rects.begin();

	int intersect_counter =  0;

	RELEASE_MESSAGE( format_string("m_rect size %i\n", m_rects.size()).c_str() );

	t_screen_rect intersect_rect;

	int avg_width=0;
	int avg_height=0;

	int duplicate_count = 0;

	int half_count = m_rects.size()/2 + 1;
	int count = 0;

	while(outer_iterator != m_rects.end())
	{
		inner_iterator = outer_iterator;
		inner_iterator++;
		count++;

		if (count == half_count) 
			break;

		while(inner_iterator != m_rects.end())
		{
			if (::intersect(*outer_iterator,*inner_iterator))
			{
				t_screen_rect outer = *outer_iterator;
				t_screen_rect inner = *inner_iterator;

				intersect_rect = ::intersection(outer,inner);
				
				if (outer == inner)
				{
					duplicate_count++;

					if (outer.contains(inner))
					{
						int containment = 1;
					}
				}

				if (intersect_rect.width() > 0 && intersect_rect.height() > 0)
				{
					//RELEASE_MESSAGE( format_string("OUT : %i l, %i t, %i r, %i b \n", outer.left, outer.top, outer.right, outer.bottom).c_str() );
					//RELEASE_MESSAGE( format_string("IN  : %i l, %i t, %i r, %i b \n", inner.left, inner.top, inner.right, inner.bottom).c_str() );

					avg_width += intersect_rect.width();
					avg_height += intersect_rect.height();
					intersect_counter++;
				}
			}
			
			inner_iterator++;
		}

		outer_iterator++;
	}

	if (intersect_counter > 0 || duplicate_count > 0)
	{
		RELEASE_MESSAGE( format_string("%i intersections within the rect list\n", intersect_counter).c_str() );
		RELEASE_MESSAGE( format_string("%i duplicates\n", duplicate_count).c_str() );
		RELEASE_MESSAGE( format_string("%i x %i avg_width x avg_height\n", avg_width/intersect_counter, avg_height/intersect_counter).c_str() );
	}


	return;

	//check if the rect is sorted in the right bin.
	//typedef std::list<t_screen_rect>::iterator					t_rect_iterator;
	//typedef std::list<t_rect_iterator>							t_rect_iterator_list;

	int bin_sort_wrong = 0;

	std::vector<t_quadtree_node>::iterator   quad_node_iterator = m_quadtree_array.begin();

	m_parent_node.rect_iterator_list.clear();

	while(quad_node_iterator != m_quadtree_array.end())
	{
		if (!quad_node_iterator->rect_iterator_list.empty())
		{
			t_rect_iterator_list::iterator	rect_iter = quad_node_iterator->rect_iterator_list.begin();
			
			while ( rect_iter != quad_node_iterator->rect_iterator_list.end() )
			{
				if (!::intersect(quad_node_iterator->area,**rect_iter))
				{
					bin_sort_wrong++;
				}
				
				rect_iter++;
			}
		}

		quad_node_iterator++;
	}

	if (bin_sort_wrong > 0)
	{
		RELEASE_MESSAGE( format_string("%i intersections within the rect list\n", bin_sort_wrong).c_str() );
	}

	//check the dimensions of all of the quadnodes to make sure they are consistent.

	/*

	//check intersect test ///////////////////////////////////

	int size = m_rects.size();

	t_screen_rect query_area;
	t_rect_list   results;

	g_node_searched=0;
	g_rects_seached=0;

	query_area.top		= 0;
	query_area.left		= 0;
	query_area.bottom	= 1280-1;
	query_area.right	= 1024-1;

	intersect(query_area,results);
	
	size = results.size();
	
	g_node_searched=0;
	g_rects_seached=0;

	results.clear();
	query_area.top		= 0;
	query_area.left		= 0;
	query_area.bottom	= 1280/2;
	query_area.right	= 1024/2;
	
	intersect(query_area,results);
	
	size = results.size();
	
	g_node_searched=0;
	g_rects_seached=0;

	results.clear();
	query_area.top		= 0;
	query_area.left		= 0;
	query_area.bottom	= 1280/4;
	query_area.right	= 1024/4;
	
	intersect(query_area,results);
	
	size = results.size();
	
	g_node_searched=0;
	g_rects_seached=0;

	results.clear();
	query_area.top		= 0;
	query_area.left		= 0;
	query_area.bottom	= 1280/8;
	query_area.right	= 1024/8;
	
	intersect(query_area,results);
	
	size = results.size();

	g_node_searched=0;
	g_rects_seached=0;

	results.clear();
	query_area.top		= 0;
	query_area.left		= 0;
	query_area.bottom	= 1280/16;
	query_area.right	= 1024/16;
	
	intersect(query_area,results);
	
	size = results.size();

	//check intsertion test ///////////////////////////////////

	t_clip_list			control_clip_list;
	t_rect_iterator		iter;
	
	for(iter = m_rects.begin(); iter != m_rects.end(); iter++)
	{
		control_clip_list += *iter;
	}

	t_clip_list::t_iterator	 clip_iter;
	int control_clip_size = 0;

	t_sorted_clip_list		control_sort_list(4,query_area);
	int list_error = 0;

	for(clip_iter = control_clip_list.begin(); clip_iter != control_clip_list.end(); clip_iter++)
	{
		control_sort_list.insert(*clip_iter, true);

		if (clip_iter->width() <= 0 || clip_iter->height() <= 0)
			list_error++;		

		control_clip_size++;
	}

	int cs_list_size = control_sort_list.m_rects.size();

	list_error = 0;
	
	for(iter = control_sort_list.m_rects.begin(); iter != control_sort_list.m_rects.end(); iter++)
	{
		if (iter->width() <= 0 || iter->height() <= 0)
			list_error++;		
	}
	
	list_error = 0;
	
	//check remove test ///////////////////////////////////
	g_node_searched=0;
	g_rects_seached=0;
	control_clip_size=0;

	//query_area.top		= 0;
	//query_area.left		= 0;
	//query_area.bottom	= 1280-1;
	//query_area.right	= 1024-1;

	query_area.top		= 0;
	query_area.left		= 0;
	query_area.bottom	= 1280/8;
	query_area.right	= 1024/8;

	control_sort_list.remove(query_area);

	control_clip_list -= query_area;

	size = control_sort_list.m_rects.size();

	for(clip_iter = control_clip_list.begin(); clip_iter != control_clip_list.end(); clip_iter++)
		control_clip_size++;

	g_node_searched=0;
	g_rects_seached=0;

	results.clear();
	query_area.top		= 0;
	query_area.left		= 0;
	query_area.bottom	= 1280/2;
	query_area.right	= 1024/2;
	
	control_sort_list.remove(query_area);
	
	size = control_sort_list.m_rects.size();
	
	g_node_searched=0;
	g_rects_seached=0;

	results.clear();
	query_area.top		= 0;
	query_area.left		= 0;
	query_area.bottom	= 1280/4;
	query_area.right	= 1024/4;
	
	control_sort_list.remove(query_area);
	
	size = control_sort_list.m_rects.size();
	
	g_node_searched=0;
	g_rects_seached=0;

	results.clear();
	query_area.top		= 0;
	query_area.left		= 0;
	query_area.bottom	= 1280/8;
	query_area.right	= 1024/8;
	
	control_sort_list.remove(query_area);
	
	size = control_sort_list.m_rects.size();

	g_node_searched=0;
	g_rects_seached=0;

	results.clear();
	query_area.top		= 0;
	query_area.left		= 0;
	query_area.bottom	= 1280/16;
	query_area.right	= 1024/16;
	
	control_sort_list.remove(query_area);
	
	size = control_sort_list.m_rects.size();

	*/

	return;
}
